'''
Company: TWL
Author: xue jian
Email: xuejian@kanzhun.com
Date: 2020-10-27 18:17:00
'''
#
# @lc app=leetcode.cn id=115 lang=python3
#
# [115] 不同的子序列
#

# @lc code=start
class Solution:
    def numDistinct(self, s: str, t: str) -> int:
        dp = [[0]*(len(s)+1) for _ in t+'0']
        dp[0] = [1]*len(dp[0])
        for i in range(1, len(dp)):
            for j in range(1, len(dp[0])):
                if s[j-1]==t[i-1]:
                    dp[i][j] += dp[i][j-1]
                    dp[i][j] += +dp[i-1][j-1]
                else:
                    dp[i][j] += dp[i][j-1]
        # print(dp)
        return dp[-1][-1]
# @lc code=end

if __name__ == "__main__":
    solution = Solution()
    s = 'rabbbit'
    t = 'rabbit'
    print(solution.numDistinct(s, t))